package 动态规划.可dp可二分;

import org.junit.Test;

import java.util.Objects;

/**
 * @author aodre , QQ : 480029069
 * @date 2022/12/10 12:44
 */
public class MinMax再思考 {
    /*
     *leetcode 410 问题的 一个 小小的 新的思考
     * 在 basecase 方面的优化
     */

    public static int solution(int nums[], int k) {
        int len = nums.length;
        int preSum[] = new int[len + 1];
        for (int i = 0; i < len; i++) {
            preSum[i + 1] = preSum[i] + nums[i];
        }
        return recursion(0, k, len - 1, preSum);
    }

    private static int recursion(int index, int k, int r, int[] preSum) {
//        if(index == r)
//            return k == 1 ? preSum[index + 1] - preSum[index] : 0;
        // 上面这个basecase 是可以直接省掉的！
        if (k == 1)
            return preSum[r + 1] - preSum[index];
        int ans = Integer.MAX_VALUE;
        for (int scale = 1; index + scale <= r; scale++) {
            ans = Math.min(ans, Math.max(preSum[index + scale] - preSum[index], recursion(index + scale, k - 1, r, preSum)));
        }
        return ans;

    }


    /*
     2023/3/24 更新二分 查找的解法！
     */


    public int solutionBinary(int nums[], int m) {
        int l = 0, r = 1000000000;
        while (l < r) {
            int mid = l + r >> 1;
            if (check(nums, mid) > m) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }
    /*
     这个 check 函数，的逻辑 还是挺抽象的！
     注意这里的 l = 0， r = 1000000000；
     是一个模拟的 区间（所有可能的区间）
     其实 给出一个 数组的话， 真正的区间是 l = max(nums[i]) , r = sum(nums[i])
     这个是真正的区间, 但是没必要这样写 , 因为 二分 非常快 ()
     */
    private int check(int[] nums, int mid) {
        int count = 0,sum = 0;
        for(int i = 0;i < nums.length;i++){
            /*
             下面这个 条件 必须要写上, 答案一定是 >= max(nums[i]) 的
             */
            if(nums[i] > mid){
                return nums.length + 1;
            }
            if(sum + nums[i] > mid){
                count++;
                sum = 0;
            }
            sum += nums[i];
        }
        return count + 1;
    }



    @Test
    public void test(){
//        int nums[] = {7,2,5,10,8},k = 2;
        //int nums[] = {1,4,4},k = 3; // 特殊 case
        int nums[] = {2,3,1,2,4,3}, k = 5;
        System.out.println(solutionBinary(nums,k));
        System.out.println(Math.pow(2,31) > 1_000_000_000);
        System.out.println(Math.pow(2,31));
        System.out.println(Integer.MAX_VALUE);
    }


    public static void main(String[] args) {
        Ego ego = new Ego();
        ego.value = 10;
        ego.str = "120";
        System.out.println(ego.hashCode());


        ego.value = 20;
        System.out.println(ego.hashCode());


        ego.str = "30";
        System.out.println(ego.hashCode());
        System.out.println(-10 >>> 1);
        System.out.println(-10 >> 1);
    }

    static class Ego{
        int value;
        String str;


        @Override
        public int hashCode() {
            return Objects.hash(this.str,this.value);
        }

        @Override
        public boolean equals(Object obj) {
            // ..... 根据 和 hashcode 使用相同的字段进行比较的规则!
            Objects.equals(this,obj); // 注意这个 工具类中equals 的实现非常的粗糙!
            return true;
        }
    }

}



